/**
 * 
 */
package string.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 * 
 * 
 * 说是有一密码锁， 4位密码,每位可以是0到9. 说有一小偷, 找到了个万能密码 可以把城里所有密码锁打开
 * 1.）万能密码最短多少， 最长多少
 * 2.）写出程序产生最短万能密码
 * 
 * 找一个最短串能包括所有的可能4位字符的组合
 * 
 * 前几天群里还讨论了一个题，不知道是不是类似，也是尝试密码的，4位密码，尝试完一个密码后，只能向左shift，移出一个数，后面再补一个数，问怎么弄使得尝试次数最少
 */
public class UniversalPassword {

	/*
	 * 图的解法好像可以，我的想法是每个node是一个密码,node之间如果有3个数子overlap就建一个edge，答案就是一个DFS或者BFS遍历
	 * 我刚才说的那个图的思路，需要修正一下，建立edge的规则：检查当前node的后三位是否和某个node的前三位相同，相同则加一条边，这样从第一个node DFS遍历即可得到解
	 */
	static class Node {
		int color = 0;
		String value = null;
		ArrayList<Node> adj = new ArrayList<Node>();

		boolean canConnect(Node n) {
			if (value.substring(1, 4).equals(n.value.substring(0, 3)))
				return true;
			else
				return false;
		}

		public String toString() {
			return value;
		}
	}

	static class Graph {
		Node[] nodes = new Node[10000];
	}

	public static Graph buildGraph() {
		Graph g = new Graph();
		for (int i = 0; i < 10000; ++i) {
			g.nodes[i] = new Node();
			g.nodes[i].value = String.format("%04d", i);
		}
		for (int i = 0; i < 10000; ++i) {
			Node v = g.nodes[i];
			for (int j = 0; j < 10000; ++j) {
				Node u = g.nodes[j];
				if (i != j) {
					if (v.canConnect(u))
						v.adj.add(u);
				}
			}
		}
		return g;
	}

	public static void DFS(Node v, StringBuilder sb) {
		v.color = 1;
		for (Node n : v.adj) {
			if (n.color == 0) {
				sb.append(n.value.charAt(3));
				DFS(n, sb);
			}
		}
	}

	public static void solve() {
		Graph g = buildGraph();
		StringBuilder sb = new StringBuilder();
		sb.append(g.nodes[0].value);
		DFS(g.nodes[0], sb);
		System.out.print(sb.length());
	}

	/*
	 * 我的代码是append最后一个数9999导致的问题，答案是...89990009999，但是0009,0099,0999已经在前面出现过了，最后一个append没办法剔除这三个数，应为要保证9999在里面，所以答案因该是...8999[9]000，把最后一个9加到[9]的位置，这样是10003
	 */
	public int minLength(int length) {
		StringBuilder sb = new StringBuilder();
		int size = (int) Math.pow(10, length) - 1;
		String pattern = "%0" + length + "d";
		sb.append(String.format(pattern, 0));
		System.out.printf("%s\n", sb.toString());
		for (int i = 1; i <= size; i++) {
			String s = String.format(pattern, i);
			System.out.printf("%s\n", s);
			if (sb.indexOf(s) >= 0)
				continue;
			int len = sb.length();
			for (int j = 4; --j >= 0;)
				if (s.indexOf(sb.substring(len - j)) == 0) {
					sb.append(s.substring(j));
					break;
				}
		}
		System.out.println(sb.length());
		return sb.length();
	}

	/**
	 * 
	 */
	public UniversalPassword() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		UniversalPassword.solve();
		//		UniversalPassword up = new UniversalPassword();
		//		up.minLength(4);
	}

}
